package com.jiangwz.sort;

import java.util.Arrays;

/**
 * 单轴快排
 * 以轴为对称, 小于轴的和大于轴的数进行交换
 * @author jiangwz
 * @create 2021/3/18.
 */
public class QuickSort extends BaseSort {

    public static void main(String[] args) {

//        int[] arr = new int[]{4, 6};
//        int[] arr = new int[]{9, 1, 8, 2, 5, 6, 3, 7, 4};
        int[] arr = randomArray(10000);
        int[] copyOf = Arrays.copyOf(arr, arr.length);
        print(arr);
        sort(arr, 0, arr.length - 1);
        print(arr);

        boolean sort = checkSort(copyOf, arr);
        System.out.println(sort);

    }

    public static void sort(int[] arr, int leftBound, int rightBound) {
        if (leftBound >= rightBound) return;
        int mid = partition(arr, leftBound, rightBound);
        sort(arr, leftBound, mid - 1);
        sort(arr, mid + 1, rightBound);
    }

    public static int partition(int[] arr, int leftBound, int rightBound) {
        int pivot = arr[rightBound];
        int left = leftBound;
        int right = rightBound - 1;
        while (left <= right) {
            while (left <= right && arr[left] <= pivot) left++;
            while (left <= right && arr[right] >= pivot) right--;

            if (left < right)
                swap(arr, left, right);
        }
        swap(arr, left, rightBound);
        return left;
    }



}
